#include <iostream>
#define MAX_T 1005
#define MAX_A 100005
#define MOD 1000000
using namespace std;
int T, A, S, B;

int kind[MAX_T];
int dp[MAX_T][MAX_A];
void solve();

int main() {
    cin >> T >> A >> S >> B;
    int t;
    for (int i = 0; i < A; i++) {
        cin >> t; kind[t]++;
    }
    solve();
    return 0;
}

void solve() {
    for (int i = 0; i <= T; i++) dp[i][0] = 1;
    for (int i = 1; i <= T; i++) {
        for (int j = 1; j <= A; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + MOD) % MOD;
            if (j - kind[i] - 1 >= 0) dp[i][j] = (dp[i][j] - dp[i - 1][j - kind[i] - 1] + MOD) % MOD;
        }
    }

    int res = 0;
    for (int i = S; i <= B; i++) {
        res = (res + dp[T][i] + MOD) % MOD;
    }
    cout << res << endl;
}